//! \file		Graphe.h
//! \brief		Définition de l'interface pour un graphe générique
//! \author		Jean-Simon Garneau & Simon Falardeau
//! \version	2.0 graphe template
//! \date		Novembre 2013

#include <iostream>
#include <fstream>		// Pour les fichiers
#include <stdexcept>
#include <algorithm>
#include <string>
#include <vector>
#include <iterator>
#include <list>
#include <limits>
#ifndef GRAPHE__H
#define GRAPHE__H


namespace tp2
{
//! \class	Graphe
//! \brief	Classe représentant un graphe orienté, coloré dont les  étiquettes sont des comparables
template<typename Objet>
class Graphe
{
private:

	// �������������������������������������������������������������������������������������������������
	//	Classes internes
	// _________________________________________________________________________________________________

	class Arc;

	//! \class	Sommet
	//! \brief	Classe représentant un sommet dans un graphe
	class Sommet
	{
	public:

		Sommet(int numero, const Objet& etiquette);
		Sommet(Sommet * source);

		~Sommet();

		int m_numero;
		Objet m_etiquette;

		Arc* m_listeDest;

		bool m_etat;
		Sommet* m_predecesseur;
		int m_cout;

		Sommet* m_precedent;
		Sommet* m_suivant;
	};

	//! \class	Arc
	//! \brief	Classe interne représentant un arc entre deux sommets dans le graphe.
	class Arc
	{
	public:

		Arc(Sommet* dest, int cout);
		~Arc();

		Sommet* m_dest;
		int m_cout;
		Arc* m_suivDest;
	};

public:

	//******************************
	//	Constructeurs et destructeur

	Graphe();
	Graphe(const Graphe &source);

	~Graphe();

	// ******************************************
	//	Ajout/suppression de sommets et d'arcs

	void ajouterSommet(int numero, const Objet& etiquette);
	void ajouterSommet(Sommet& sommet);
	void enleverSommet(int numero);

	void ajouterArc(int numOrigine, int numDestination, int cout);
	void enleverArc(int numOrigine, int numDestination);

	//	****************************************************
	//	Données sur le graphe (incluant listes de sommets)

	int nombreSommets() const;
	bool estVide() const;
	std::vector<int> listerSommets() const;
	std::vector<Objet> listerEtiquetteSommets() const;

	// ************************
	//	Trouver numéro sommet

	int	getNumeroSommet(const Objet& etiquette) const;

	// **********************************
	//	Données à propos des sommets

	bool sommetExiste(int numero) const;
	bool etiquetteExiste(Objet etiquette) const;
	Objet getEtiquetteSommet(int numero) const;
	int ordreSortieSommet(int numero) const;
	int	ordreEntreeSommet(int numero) const;
	std::vector<int> listerSommetsAdjacents(int numeroSommetsAdjacents) const;

	// ***************************
	//	Données à propos des arcs

	bool arcExiste(int numOrigine, int numDestination) const;
	int	getCoutArc(int numOrigine, int numDestination) const;

	// *************************
	//	Surcharge d'opérateurs

	const Graphe& operator =(const Graphe& source);
	template<class U>
	friend std::ostream& operator <<(std::ostream& out, const Graphe<U>& g);

	// ***************************
	//	Fonctions plus complexes

	Graphe fermetureGraphe() const;
	bool estFortementConnexe() const;
	void getComposantesFortementConnexes(
			std::vector<std::vector<Objet> > & composantes) const;
	int	bellmanFord(const Objet& eOrigine, const Objet& eDestination,
			std::vector<Objet> & chemin);
	int	dijkstra(const Objet& eOrigine, const Objet& eDestination,
			std::vector<Objet> & chemin);
	void getPointsArticulation(std::vector<Objet> & sommets);

private:

	// ********************
	//	Propriétés privées

	int nbSommets; /**< Le nombre de sommets dans le graphe */
	Sommet * listSommets; /**< Liste des sommets du graphe */

	// *********************************
	//	Méthodes auxiliaires (getters)

	Sommet* _getSommet(int numero) const;
	Arc* _getArc(Sommet * sommet1, Sommet * sommet2) const;

	// **********************************************
	//	Méthodes auxiliaires (destruction + copie)

	void _detruireGraphe();
	void _copierGraphe(const Graphe &source);
	void _enleverSommet(Sommet * sommetAEnlever);

	// ***************************************
	//	Méthodes auxiliaires (path finding)

	void _initPathFinding(const Objet& eOrigine, const Objet& eDestination,
			Sommet * & origine, Sommet * & destination);
	void _recupererChemin(Sommet * destination, std::vector<Objet> & chemin);

};
#include "Graphe.hpp"
}
#endif
